/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/segment-tree-build-ii
   @Language: C++
   @Datetime: 16-02-09 08:30
   */

/**
 * Definition of SegmentTreeNode:
 * class SegmentTreeNode {
 * public:
 *     int start, end, max;
 *     SegmentTreeNode *left, *right;
 *     SegmentTreeNode(int start, int end, int max) {
 *         this->start = start;
 *         this->end = end;
 *         this->max = max;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
	SegmentTreeNode * buildcore(vector<int> &A, int start, int end){
		SegmentTreeNode *root=new SegmentTreeNode(start,end,A[start]);
		if(start==end) return root;
		root->left=buildcore(A,start,(start+end)/2);
		root->right=buildcore(A,(start+end)/2+1,end);
		root->max=max(root->left->max,root->right->max);
		return root;
	}
public:
	/**
	 * @param A: a list of integer
	 * @return: The root of Segment Tree
	 */
	SegmentTreeNode * build(vector<int> &A) {
		// write your code here
		if (A.size()<1) return NULL;
		return buildcore(A,0,A.size()-1);
	}
};
